/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/bold-words-in-string
   @Language: C++
   @Datetime: 20-01-19 11:12
   */

class Solution {
public:
	/**
	 * @param words: the words
	 * @param S: the string
	 * @return: the string with least number of tags
	 */
	string boldWords(vector<string> &words, string &S) {
		// Write your code here
		unordered_set<string> dict(words.begin(), words.end());
		vector<bool> flags(S.length(), false);
		int minlen=10, maxlen=1;
		for(const auto &s:words){
			minlen = min(minlen, (int)s.length());
			maxlen = max(maxlen, (int)s.length());
		}
		for(int i=0; i<S.length(); ++i){
			for(int len=minlen; len<=maxlen && i+len<=S.length(); ++len){
				if (dict.count(S.substr(i, len)))
					for(int j=0; j<len; flags[i+j++]=true);
			}
		}
		string str;
		for(minlen=maxlen=0; minlen<flags.size(); ++minlen){
			if (flags[minlen]){
				if (!maxlen){
					str.append("<b>");
					maxlen=1;
				}
			}
			else{
				if (maxlen){
					str.append("</b>");
					maxlen=0;
				}
			}
			str.push_back(S[minlen]);
		}
		if (maxlen) str.append("</b>");
		return str;
	}
};
